package swordmeansoffer;

/**
 * @BelongsProject: LeetCode
 * @BelongsPackage: swordmeansoffer
 * @Author: elvis
 * @CreateTime: 2020-10-07 21:42
 * @Description: 剑指 Offer 46. 把数字翻译成字符串
 * 给定一个数字，我们按照如下规则把它翻译为字符串：0 翻译成 “a” ，1 翻译成 “b”，……，11 翻译成 “l”，……，25 翻译成 “z”。一个数字可能有多个翻译。请编程实现一个函数，用来计算一个数字有多少种不同的翻译方法。
 *
 *
 *
 * 示例 1:
 *
 * 输入: 12258
 * 输出: 5
 * 解释: 12258有5种不同的翻译，分别是"bccfi", "bwfi", "bczi", "mcfi"和"mzi"
 *
 *
 * 提示：
 *
 * 0 <= num < 2^31
 */
public class SMO46 {

    /**
     * 这是一道典型的动态规划题目。对于一个数 num[i]，我们有两种选择：
     *
     * 只翻译自己；
     * 和前面的数字组合翻译，前提是组合的数在 10-25 之间。
     * 我们可以用 dp(i) 表示前 i 个数字的翻译方法数。根据以上两种选择，我们进行如下分析：
     *
     * 如果只翻译自己，比如 12345，如果 5 单独翻译，那么方法数与 1234 是一样的， dp(i)=dp(i-1)
     * 如果和前面的数字组合，比如 1235，如果 35 组合翻译，从两方面考虑：
     * 35看成一个整体，虽然加了 5 但是和没加是一样的，状态 dp(i)=dp(i-1)
     * 35组合就意味着不能再组合了，相当于条件 1 中的单独翻译自己，方法数与 12 是一样的。这时 dp(i)=dp(i-2)
     * 以上两种情况相加即可。
     * 故状态转移函数为：
     *
     *           dp(i−2)+dp(i−1)
     * dp(i)={
     *           dp(i−1)
     *
     * 再考虑边界条件：
     *
     * dp(0)=dp(1)=1
     */
    public int translateNum(int num) {
        if (num < 10) {
            //个位数,只可能有一种翻译法
            return 1;
        }
        char[] nums = String.valueOf(num).toCharArray();
        //dp[i]代表前i-1个数总共有多少种翻译方法
        int[] dp = new int[nums.length];
        dp[0] = 1;
        int n = (nums[0] - '0') * 10 + (nums[1] - '0');
        //计算初始值,第二位数和第一位数组成的数字介于(9,26)之间,有两种翻译
        //若组成的数是0~9或大于25则只能有一种翻译
        dp[1] = n > 9 && n < 26 ? 2 : 1;

        for (int i = 2; i < nums.length; i++) {
            //计算当前数和前一个数组成的数值大小,如1225的下标3的数和它前一个数组成的值为25
            n = (nums[i - 1] - '0') * 10 + (nums[i] - '0');
            if (n > 9 && n < 26) {
                //组成数值处于(9,26)范围内,则可翻译的方法数为前两个数的翻译总和
                dp[i] = dp[i - 1] + dp[i - 2];
            } else {
                //组成数值不在(9,26)范围内，则只能算一种翻译,和前一个数能翻译的方法数一样
                dp[i] = dp[i - 1];
            }
        }
        return dp[nums.length - 1];
    }
}
